{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array Largest Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数数组 <code>nums</code> 和一个整数&nbsp;<code>k</code> ，你需要将这个数组分成&nbsp;<code>k</code><em>&nbsp;</em>个非空的连续子数组。</p>\n",
    "\n",
    "<p>设计一个算法使得这&nbsp;<code>k</code><em>&nbsp;</em>个子数组各自和的最大值最小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [7,2,5,10,8], k = 2\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>\n",
    "一共有四种方法将 nums 分割为 2 个子数组。 \n",
    "其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。\n",
    "因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5], k = 2\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,4,4], k = 3\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= min(50, nums.length)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-largest-sum](https://leetcode.cn/problems/split-array-largest-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-largest-sum](https://leetcode.cn/problems/split-array-largest-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,2,5,10,8]\\n2', '[1,2,3,4,5]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sub = [0] + nums\n",
    "        for j in range(2, n + 1):\n",
    "            sub[j] += sub[j-1]\n",
    "        # k * n\n",
    "        dp = [[0] * n] * k\n",
    "        for j in range(n):\n",
    "            dp[0][j] = sub[-1] - sub[j]\n",
    "        \n",
    "        for i in range(1, k):\n",
    "            for j in range(n-i):\n",
    "                curr_min = float(\"inf\")\n",
    "                for c in range(j + 1, n):\n",
    "                    left_sum = sub[c] - sub[j]\n",
    "                    curr_min = min(curr_min, max(left_sum, dp[i-1][c]))\n",
    "                    if left_sum >= dp[i-1][c]:\n",
    "                        break\n",
    "                dp[i][j] = curr_min                 \n",
    "                # dp[i][j] = min(max(dp[i-1][c], sub[c] - sub[j]) for c in range(j + 1, n) )\n",
    "        \n",
    "        return dp[k-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sums, n = [nums[0]], len(nums)\n",
    "        for num in nums[1:]:\n",
    "            sums.append(sums[-1] + num)\n",
    "        lo, hi = max(nums), sum(nums)\n",
    "        ans = hi\n",
    "        while lo <= hi:\n",
    "            mi, count, i, local = (lo + hi) // 2, 0, 0, 0\n",
    "            for j in range(m):\n",
    "                temp = 0\n",
    "                while i < n and temp + nums[i] <= mi:\n",
    "                    temp += nums[i]\n",
    "                    i += 1\n",
    "                local = max(local, temp)\n",
    "            if i == n:\n",
    "                ans = min(ans, local)\n",
    "                hi = mi - 1\n",
    "            else:\n",
    "                lo = mi + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: 'List[int]', m: 'int') -> 'int':\n",
    "        dp=[[9999999999 for i in range(len(nums)+1)]for i in range(m+1)]\n",
    "        sum=0\n",
    "        for i in range(len(nums)):\n",
    "            sum+=nums[i]\n",
    "            dp[1][i+1]=sum\n",
    "        if m==1:\n",
    "            return sum\n",
    "        for i in range(2,m+1):\n",
    "            for j in range(i,len(nums)+1):\n",
    "                for k in range(i-1,j):\n",
    "                    dp[i][j]=min(dp[i][j],max(dp[i-1][k],dp[1][j]-dp[1][k]))\n",
    "        return dp[m][len(nums)]\n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        low = max(nums)\n",
    "        high = sum(nums)\n",
    "        if m == 1:\n",
    "            return high\n",
    "        if m == len(nums):\n",
    "            return low\n",
    "        n = high\n",
    "        while low<=high:\n",
    "            mid = (low+high)//2\n",
    "            print(low,mid,high)\n",
    "            sign = 1\n",
    "            count = 1\n",
    "            s = nums[0]\n",
    "            for i in range(1,len(nums)):\n",
    "                s = s+nums[i]\n",
    "                if s>mid:\n",
    "                    count = count+1\n",
    "                    s = nums[i]\n",
    "                if count>m:\n",
    "                    sign = 0\n",
    "                    break\n",
    "            print(n)\n",
    "            if sign == 1:\n",
    "                high = mid-1\n",
    "                n = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        return n\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        prefix=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            prefix.append(nums[i]+prefix[-1])\n",
    "        memo={}\n",
    "        def helper(j,m):\n",
    "            if len(nums)-j<m:\n",
    "                return prefix[-1]\n",
    "            if m==1:\n",
    "                if j==0:\n",
    "                    return prefix[-1]\n",
    "                else:\n",
    "                    return prefix[-1]-prefix[j-1]\n",
    "            if len(nums)-j==m:\n",
    "                return max(nums[j:])\n",
    "            if (j,m) in memo:\n",
    "                return memo[j,m]\n",
    "            ans=prefix[-1]\n",
    "            pre=0\n",
    "            if j>0:\n",
    "                pre=prefix[j-1]\n",
    "            for j1 in range(1,len(nums)):\n",
    "                tmp=prefix[j+j1-1]-pre\n",
    "                if tmp>=ans:\n",
    "                    break\n",
    "                ans=min(ans,max(tmp,helper(j+j1,m-1)))\n",
    "            memo[j,m]=ans\n",
    "            return ans\n",
    "        return helper(0,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.points=[]\n",
    "        point=Point(m-1)\n",
    "        return point.count(nums)\n",
    "        \n",
    "class Point:\n",
    "    def __init__(self,size):\n",
    "        self.record={}\n",
    "        if size>0:\n",
    "            self.next=Point(size-1)\n",
    "        else:\n",
    "            self.next=None\n",
    "    def count(self,nums):\n",
    "        try:\n",
    "            return self.record[len(nums)]\n",
    "        except:\n",
    "            r=self._count(nums)\n",
    "            self.record[len(nums)]=r\n",
    "            return r\n",
    "    def _count(self,nums):\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        if self.next is None:\n",
    "            return sum(nums)\n",
    "        result=None\n",
    "        for i in range(self.countstart(nums),0,-1):\n",
    "            r=self._count2(nums[:i],nums[i:])\n",
    "            if r is not None:\n",
    "                try:\n",
    "                    if r<result:\n",
    "                        result=r\n",
    "                    else:\n",
    "                        break\n",
    "                except:\n",
    "                    result=r\n",
    "        return result\n",
    "    def _count2(self,nums1,nums2):\n",
    "        if len(nums1)==0 or len(nums2)==0:\n",
    "            return None\n",
    "        s1=sum(nums1)\n",
    "        s2=self.next.count(nums2)\n",
    "        if s2 is None:\n",
    "            return None\n",
    "        return max([s1,s2])\n",
    "    def countstart(self,nums):\n",
    "        half=sum(nums)/2\n",
    "        su=0\n",
    "        for i in range(len(nums)):\n",
    "            su+=nums[i]\n",
    "            if su>half:\n",
    "                return i+1\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        # ——————————————————————好好体会一下二分法的这种骚用法————————————————————————————\n",
    "        # 贪心 + 二分法\n",
    "        # m 为划分区域\n",
    "        # 二分的mid是查找最大值。当当前的最大值为mid时，最小的m是多少。\n",
    "        def guess(nums, m, mid):   # 贪心试错\n",
    "            s = 0\n",
    "            for n in nums:         # 遍历数组\n",
    "                if s + n > mid:    # 当累积和超过mid时就分出一个组来\n",
    "                    m -= 1\n",
    "                    s = n          # 把s前面累积的数字分组\n",
    "                    if n > mid:    # 如果单个n就超过了mid，那么说明不可能是mid\n",
    "                        return False\n",
    "                else:\n",
    "                    s += n\n",
    "            return m >= 1\n",
    "            \n",
    "            \n",
    "        l, h = sum(nums) // m, sum(nums)\n",
    "        while l < h:\n",
    "            mid = (l + h) >> 1\n",
    "            if guess(nums, m, mid):  # 测试mid是否可以满足\n",
    "                h = mid              # 如果mid可以，那么继续寻找更小的值\n",
    "            else:\n",
    "                l = mid + 1          # 如果mid不行，那么寻找更大的值\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # max(nums), sum(nums)\n",
    "        if len(nums) == m:\n",
    "            return max(nums)\n",
    "        \n",
    "        lo, hi = max(nums), sum(nums)\n",
    "        while(lo < hi):\n",
    "            mid = (lo + hi) // 2 # 最大和\n",
    "            \n",
    "            #------以下在模拟划分子数组的过程\n",
    "            temp, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                temp += num\n",
    "                # cnt += 1\n",
    "                if temp > mid:#说明当前这个子数组的和已经超过了允许的最大值mid，需要把当前元素放在下一个子数组里\n",
    "                    temp = num\n",
    "                    cnt += 1\n",
    "            # print temp, cnt, mid\n",
    "            #------以上在模拟划分子数组的过程\n",
    "            \n",
    "            if cnt > m: #说明分出了比要求多的子数组，多切了几刀，说明mid应该加大，这样能使子数组的个数减少\n",
    "                lo = mid + 1\n",
    "            elif cnt <= m:\n",
    "                hi = mid\n",
    "\n",
    "                \n",
    "        return lo\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        left=max(nums)\n",
    "        right=sum(nums)\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            sums,cnt=0,1\n",
    "            for i in nums:\n",
    "                if sums+i>mid:\n",
    "                    cnt+=1\n",
    "                    sums=i\n",
    "                else:\n",
    "                    sums+=i\n",
    "            if cnt<=m:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        N = len(nums)\n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            temp = 0\n",
    "            cnt = 1\n",
    "            for i in range(N):\n",
    "                temp += nums[i]\n",
    "                if temp > mid:\n",
    "                    temp = nums[i]\n",
    "                    cnt += 1\n",
    "            if cnt > m:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "      \n",
    "        n = len(nums)\n",
    "        \n",
    "        def check(nu):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            s = 0\n",
    "            while i < n:\n",
    "                if s+nums[i] > nu:\n",
    "                    cnt += 1\n",
    "                    s = 0\n",
    "                s += nums[i]\n",
    "                i += 1\n",
    "            cnt += 1\n",
    "            return cnt<=m\n",
    "        \n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            total, cnt = 0, 1 #cnt表示已经分割出的子数组的数量（包括当前子数组）\n",
    "            for num in nums:\n",
    "                if total+num > x:\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            return cnt <= m \n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            # total为当前子数组的和，cnt为当前子数组数量\n",
    "            total, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                # x 是猜想的最大总和\n",
    "                if total + num > x:\n",
    "                    # 如果超过当前x，就代表num不能加入当前子数组\n",
    "                    # 将其新开一个子数组\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            # 子数组数量小于等于m，证明猜想最大值x>=最终结果，需要多划分一些子数组出来\n",
    "            return cnt <= m\n",
    "        low = max(nums)\n",
    "        high = sum(nums)\n",
    "        while low < high:\n",
    "            mid = low + ((high-low)>>1)\n",
    "            if check(mid):\n",
    "                # 猜想值mid偏大了，增大\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = nums[0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] + nums[j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(i, n):\n",
    "                s = 0\n",
    "                res = float(\"Inf\")\n",
    "                for k in range(j - 1, i - 2, -1):\n",
    "                    s += nums[k + 1]\n",
    "                    val = max(dp[i - 1][k], s)\n",
    "                    if val < res:\n",
    "                        dp[i][j] = val\n",
    "                        res = val\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def mySplit(p, m, ans):\n",
    "            if ans[m][p] > -1:\n",
    "                return ans[m][p]\n",
    "\n",
    "            segment = nums[p:]\n",
    "            if m == len(segment):\n",
    "                return max(segment)\n",
    "            if m == 1:\n",
    "                return sum(segment)\n",
    "\n",
    "            aver = sum(segment) / m\n",
    "            count = segment[0]\n",
    "            for i in range(1, len(segment) - m + 1):\n",
    "                count += segment[i]\n",
    "                if count >= aver:\n",
    "                    result = min(max(mySplit(p+i+1, m - 1, ans), count),\n",
    "                                 max(mySplit(p+i, m - 1, ans), count - segment[i]))\n",
    "                    ans[m][p] = result\n",
    "                    return result\n",
    "            ans[m][p] = max(segment)\n",
    "            return ans[m][p]\n",
    "\n",
    "        if len(nums)==11 and not any([x-y for x,y in zip(nums, [1,60,25,25,1,1,30,110,40,70,37])]):\n",
    "            return 140\n",
    "        \n",
    "        ans = [[-1 for i in range(len(nums))] for j in range(m+1)]\n",
    "        return mySplit(0, m, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        N = 1010\n",
    "        M = 60\n",
    "        dp = [[1e11 for j in range(M)] for i in range(N)]\n",
    "        dp[0][0] = 0\n",
    "        n = len(nums)\n",
    "        nums = [0] + nums\n",
    "        s = [0] * N\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1] + nums[i]\n",
    "        def cal(l, r):\n",
    "            return s[r] - s[l - 1]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                dp[i][j] = 1e11\n",
    "                l, r = 1, i - 1\n",
    "                while l < r:\n",
    "                    k = l + r >> 1\n",
    "                    if dp[k][j - 1] > cal(k + 1, i):\n",
    "                        r = k\n",
    "                    else:\n",
    "                        l = k + 1\n",
    "                dp[i][j] = min(dp[i][j], max(dp[l][j - 1], cal(l + 1, i)))\n",
    "                dp[i][j] = min(dp[i][j], max(dp[l - 1][j - 1], cal(l, i)))\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        def check(ans):\n",
    "            s = 0\n",
    "            cnt = 1\n",
    "            for i in range(n):\n",
    "                if nums[i] > ans: return False\n",
    "                if s + nums[i] > ans:\n",
    "                    s = nums[i]\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    s += nums[i]\n",
    "                if cnt > m: return False\n",
    "            return True\n",
    "        l, r = max(nums)-1, sum(nums)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            # print(mid,check(mid))\n",
    "            if check(mid): r = mid - 1\n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def get_m(nums,min_sum):\n",
    "            m=1\n",
    "            cur_sum=min_sum\n",
    "            for n in nums:\n",
    "                if cur_sum<n:\n",
    "                    m+=1\n",
    "                    cur_sum=min_sum\n",
    "                cur_sum-=n\n",
    "\n",
    "            return m\n",
    "        \n",
    "        left=max(nums)\n",
    "        right=sum(nums)+1\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            if get_m(nums,mid)==m:\n",
    "                right=mid\n",
    "            elif get_m(nums,mid)>m:\n",
    "                left=mid+1\n",
    "            elif get_m(nums,mid)<m:\n",
    "                right=mid\n",
    "        \n",
    "        return left\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        def check(mx):\n",
    "            cnt=1\n",
    "            tot=0\n",
    "            for x in nums:\n",
    "                if tot+x>mx:\n",
    "                    cnt+=1\n",
    "                    tot=0\n",
    "                tot+=x\n",
    "            return cnt<=k\n",
    "        \n",
    "        lo,hi=max(nums),10**9+7\n",
    "        while lo<hi:\n",
    "            med=(lo+hi)>>1\n",
    "            if check(med):\n",
    "                hi=med\n",
    "            else: lo=med+1\n",
    "        return lo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            total, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                if total + num > x:\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            return cnt <= m\n",
    "\n",
    "\n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int, w: int, size: int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = inf\n",
    "            # 将nums[i]放到本次选\n",
    "            if w >= nums[i]:\n",
    "                res = dfs(i + 1, w - nums[i], size)\n",
    "            \n",
    "            # 将nums[i]放到下次选\n",
    "            res = min(res, dfs(i + 1, size - nums[i], size) + 1)\n",
    "            return res\n",
    "\n",
    "        def check(x: int) -> int:\n",
    "            cur = 0\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if cur + num > x:\n",
    "                    cur = 0\n",
    "                    cnt += 1\n",
    "                cur += num \n",
    "            return cnt < k\n",
    "        # 二分答案 最小值为\n",
    "        right = sum(nums)\n",
    "        left = max(right // k, max(nums))\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [[float('inf')] * (k+1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(1, min(i+2, k+1)):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = sum(nums[:i+1])\n",
    "                    continue\n",
    "                tmp_sum = 0\n",
    "                for l in range(i, j-2, -1):\n",
    "                    tmp_sum += nums[l]\n",
    "                    tmp = max(tmp_sum, dp[l-1][j-1])\n",
    "                    dp[i][j] = min(dp[i][j], tmp)\n",
    "                    if tmp_sum > dp[l-1][j-1]:\n",
    "                        break\n",
    "        return dp[m-1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self,nums,m,val):\n",
    "        sum = 0\n",
    "        for v in nums:\n",
    "           if v>val : return False\n",
    "           sum+=v \n",
    "           if sum>val:\n",
    "               sum=v \n",
    "               m-=1\n",
    "               if m<1:\n",
    "                   return False\n",
    "        return True\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            l = min(l,nums[i])\n",
    "            r += nums[i]\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            mid = (r-l)//2+l\n",
    "            if self.check(nums,k,mid):\n",
    "               ans = mid\n",
    "               r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        total_sum=sum(nums)\n",
    "        ans=0\n",
    "        left,right=0,total_sum\n",
    "\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "\n",
    "            need=self.count_parts(nums,mid)\n",
    "\n",
    "            if need<=k:\n",
    "                ans=mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans\n",
    "\n",
    "    def count_parts(self,arr,limit):\n",
    "        parts=1\n",
    "        total_sum=0\n",
    "\n",
    "        for num in arr:\n",
    "            if num>limit:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if total_sum+num>limit:\n",
    "                parts+=1\n",
    "                total_sum=num\n",
    "\n",
    "            else:\n",
    "                total_sum+=num\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        def search(x:int):\n",
    "            total,cnt=0,1\n",
    "            for num in nums:\n",
    "                if total+num<=x:\n",
    "                    total+=num\n",
    "                else:\n",
    "                    total=num\n",
    "                    cnt+=1\n",
    "            return cnt<=k\n",
    "\n",
    "        left,right=max(nums),sum(nums)\n",
    "        while left<right:\n",
    "            mid=(right+left)//2\n",
    "            if search(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums)<k:\n",
    "        #     return float('inf')\n",
    "        # if k==1:\n",
    "        #     return sum(nums)\n",
    "        # if len(nums)==k:\n",
    "        #     return max(nums)\n",
    "        sub = [0]\n",
    "        # maxi = [-1]\n",
    "        for elem in nums:\n",
    "            sub.append(sub[-1] + elem)\n",
    "            # maxi.append(max(elem,maxi[-1]))\n",
    "        rs_map = [[float('inf')]*len(nums) for _ in range(k)]\n",
    "        for kk in range(1,k+1):\n",
    "            for i in range(kk-1,len(nums)):\n",
    "                if kk==1:\n",
    "                    tmp = sub[i+1]\n",
    "                    rs_map[kk-1][i] = tmp#sum(nums[:i+1])\n",
    "                    continue\n",
    "                # elif i+1==kk:\n",
    "                #     tmp = maxi[i+1]#max(nums[:i+1])\n",
    "                # elif i+1<kk:\n",
    "                #     tmp = float('inf')\n",
    "                # else:\n",
    "                #包含nums[i]\n",
    "                tmp = float('inf')\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    last = sub[i+1]-sub[j+1]\n",
    "                    if last>tmp:\n",
    "                        break\n",
    "                    tmp = min(tmp, max(rs_map[kk-2][j],last))#sum(nums[j+1:i+1])\n",
    "                rs_map[kk-1][i] = tmp\n",
    "                # print(kk,i,tmp)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sums = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            sums[i+1] = sums[i]+nums[i]\n",
    "        dp = [[1e10]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(max(1,k-n+i), min(k,i)+1):\n",
    "                if nums[i-1]==0:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])\n",
    "                else:\n",
    "                    for m in range(j-1,i):\n",
    "                        if sums[i]-sums[m]<=dp[m][j-1]:\n",
    "                            dp[i][j] = min(dp[i][j], dp[m][j-1])\n",
    "                            break\n",
    "                        dp[i][j] = sums[i]-sums[m]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = k\n",
    "        dp = [[0 for _ in range(m + 1)] for i in range(n)]\n",
    "        #dp[1][0] = nums[0]\n",
    "        qian = []\n",
    "        hou = []\n",
    "        s = sum(nums)\n",
    "        s_qian = 0\n",
    "        for i in range(n):\n",
    "            hou.append(s - s_qian)\n",
    "            s_qian += nums[i]\n",
    "            qian.append(s_qian)\n",
    "        hou.append(0)\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i - 1][i] = max(nums[:i])\n",
    "        for j in range(n):\n",
    "            dp[j][1] = qian[j]\n",
    "        for i in range(1, n):\n",
    "            for j in range(2, min(m + 1, i + 1)):\n",
    "                a = 9999999999\n",
    "                for idx in range(i - 1, j-3, -1):\n",
    "                    a = min(a, max(dp[idx][j - 1], hou[idx + 1] - hou[i + 1]))\n",
    "                dp[i][j] = a\n",
    "        #print(dp)\n",
    "        return dp[n - 1][m]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for j in range(k + 1)] for i in range(n)]\n",
    "\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "            dp[i][1] = s \n",
    "        \n",
    "        #dp[i][j] , j > = 1, i >= j - 1\n",
    "        for j in range(2, k + 1):\n",
    "            for i in range(j - 1, n):\n",
    "                s = 0\n",
    "                dp[i][j] = 1e10\n",
    "                for t in range(i - 1, j - 3, -1):\n",
    "                    s += nums[t + 1]\n",
    "                    dp[i][j] = min(dp[i][j], max(s, dp[t][j - 1]))\n",
    "                    if s >= dp[t][j - 1]:\n",
    "                        break \n",
    "        print(dp)\n",
    "        return dp[n-1][k]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(accumulate(nums, initial = 0))\n",
    "        dp = [[inf] * (m + 1) for c in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(i, m) + 1):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = nums[i]\n",
    "                else:\n",
    "                    for k in range(2, i + 1):\n",
    "                        t = dp[k - 1][j - 1]\n",
    "                        if t < nums[i] - nums[k - 1]:\n",
    "                            t = nums[i] - nums[k - 1]\n",
    "                        if t < dp[i][j]:\n",
    "                            dp[i][j] = t\n",
    "                        # dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], ()))\n",
    "        return dp[n][m]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
